#!/usr/bin/env python

import random, sys, os

class Counters:
    def __init__(self):
        self.amortie = 0
        self.prep = 0
        self.search = 0
        
    def increment(self, name):
        if name == 'search':
            self.search = self.search +1
        elif name == 'prep':
            self.prep = self.prep + 1
        else:
            print 'Invalid counter'
    
    def get_amortie(self, k):
        return self.search + self.prep/k

######################################################
# Datastructure
######################################################
class Data:
    ########################
    # Object initialization
    ########################
    def __init__(self,N,R,D):
        self.list = []
        self.hash_table = []
        self.hash_mod = None
        self.tree = RBTree()
        self.N = N
        self.R = R
        self.D = D
        self.toSearch = []
        self.Found = []
        self.cnt = Counters()
        
    def __len__(self):
        return self.N
    
    ########################
    # Encapsulation/Decapsulation methods
    ########################
    def setN(self, N):
        self.N = N
    def setR(self, R):
        self.R = R
    def setD(self, D):
        self.D = D
    def setHashMod(self, x):
        self.hash_mod = x
    def getN(self):
        return self.N
    def getR(self):
        return self.R
    def getD(self):
        return self.D
    def getList(self):
        return self.list
    def getHashMod(self):
        return self.hash_mod
    def getHashTable(self):
        return self.hash_table
    def getTree(self):
        return self.tree
        
    def PrintStats(self, fname=None):
        pass
     
    ########################
    # Data creation
    ########################
    
    def generate_data(self, N, R, D): #Done
        T = []
        Tp = []
        M = N/2
        for n in range(0, M):
            Tp.append(n+1)
        for n in range(0, N):
            T.append(random.randint(0,R))
        T.sort()
        m = M
        for n in range(1, (M*D)/100):
            k = random.randint(1,R) % m
            L = Tp[k]
            Tp[k] = Tp[m -1]
            m = m - 1
            
            tmp = T[M-L]
            T[M-L] = T[M+L-1]
            T[M+L-1] = tmp
        return T

    
    def roll(self):
        self.list = self.generate_data(self.N, self.R, self.D)
        
    def build_hash_table(self):
        if self.list == []:
            raise BaseException
        del self.hash_table
        self.hash_table = []
        if self.hash_mod == None:
            raise BaseException
            
        for i in range(0,self.hash_mod):
            self.hash_table.append([])
            
        for i in range(0,self.N):
            val = self.list[i]
            self.hash_table[val % self.hash_mod].append((val,i))
    
    def build_tree(self):
        pass
        
    ########################
    # Sorting algorithms
    ########################
    
    def sort(self, sname):
        if sname == 'quicksort':
            self.list = self.quicksort(self.list)
        elif sname == 'heapsort':
            self.heapsort(self.list, self.N)
        elif sname == 'mergesort':
            self.list = self.mergesort(self.list)
        elif sname == 'pigeonsort':
            self.list = self.pigeonsort(self.list)
        elif sname == 'radixsort':
            pass
        elif sname == 'insertsort':
            self.insertsort(self.list)
        else:
            print 'Invalid sort'
    

    def pigeonsort(self, A): #Done
        N = len(A)
        m = 0
        
        for i in range(0,N):
            if A[i] > m:
                m = A[i]
        
        T = []
        # Set all required memory to zero
        for i in range(0,m+1):
            T.append(0)
        
        # Count the amount of occurences of a single number
        for i in range(0,N):
            T[A[i]] = T[A[i]] + 1
        
        B = []
        for i in range(0,m+1):
            
            while T[i] > 0:
                B.append(i)
                T[i] = T[i] - 1
        
        return B
                

    def mergesort(self, toSort): #Done
        if len(toSort) <= 1:
            return toSort
     
        mIndex = len(toSort) / 2
        left = self.mergesort(toSort[:mIndex])
        right = self.mergesort(toSort[mIndex:])
     
        result = []
        while len(left) > 0 and len(right) > 0:
            if left[0] > right[0]:   
                result.append(right.pop(0))
            else:
                result.append(left.pop(0))
     
        if len(left) > 0:
            result.extend(self.mergesort(left))
        else:
            result.extend(self.mergesort(right))
     
        return result     



    def insertsort(self, A): #Done
        for i in range(1, len(A)):
            val = A[i]
            pos = i
            while pos > 0 and val < A[pos-1]:
                A[pos] = A[pos - 1]
                pos = pos -1
            A[pos] = val


     
    def quicksort(self, toSort): #http://errorsandexceptions.wordpress.com/2011/05/16/quicksort-and-mergesort-in-python/
        if len(toSort) <= 1:
            return toSort
     
        end = len(toSort) - 1
        pivot = toSort[end]
     
        low = []
        high = []
     
        for num in toSort[:end]:
            if num <= pivot:
                low.append(num)
            else:
                high.append(num)
     
        sortedList = self.quicksort(low)
        sortedList.append(pivot)
        sortedList.extend(self.quicksort(high))
     
        return sortedList
     
     
    def heapsort(self, A, N): #Done

            def xchg(A, src1, src2):
                    tmp = A[src1]
                    A[src1] = A[src2]
                    A[src2] = tmp

            def siftDown(A, start, end):
                    root = start
                    while (root * 2 +1) <= end:
                            child = root * 2 + 1
                            swap = root
                            if A[swap] < A[child]:
                                    swap = child
                            if (child+1 <= end) and (A[swap] < A[child+1]):
                                    swap = child + 1
                            if swap != root:
                                    xchg(A, root, swap)
                                    root = swap
                            else:  
                                    return True    


            def heapify(A, N):
                    start = (N-2) / 2
                    while start >= 0:
                            siftDown(A, start, N-1)
                            start = start - 1

            heapify(A, N)
            end = N - 1
            while end > 0:
                    xchg(A, end, 0)
                    end = end - 1
                    siftDown(A, 0, end)
            

######################################################
# Search algorithms
######################################################

    def search(self,x , aname):
        if aname == 'binary':
            print  self.search_binary(x, self.list, 0,self.N)
        elif aname == 'tree':
            pass
        elif aname == 'hash':
            print self.search_hash(x, self.hash_table, self.hash_mod)
        elif aname == 'sequential':
            print  self.search_sequential(x, self.list, self.N)
        elif aname == 'optimized':
            pass
        else:
            print 'Invalid algorithm'

    def search_tree(self):
        pass
        
    def search_optimized(self):
        if self.D == 0:
            self.search_sequential(x, self.l, self.N, start=(self.R / 100) * self.N)
        
    def search_hash(self, x, h, n):
        r = -1

        for i in range(0, len(h[x%n])):
            if h[x%n][i][0] == x:
                r = h[x%n][i][1]
                break
                       
        return r

    def search_sequential(self, x, l, N, start=0):
        r = -1
        
        for i in range(0+start,N+start):
            if l[i % N] == x:
                r = i % N
                break
                
        return r

    def search_binary(self, x, l, lo, hi):
        m = (hi+lo)/2
        
        if hi <= lo:
            return -1
        
        if l[m] > x:
            r = self.search_binary(x,l,0, m-1)
        elif l[m] < x:
            r = self.search_binary(x,l, m+1, hi)
        elif l[m] == x:
            r = m
        else:
            print 'Uh oh, shouldn\'t get here'

        return r



class RBTree(object):
    def __init__(self):
    
        self.nil = self.Node(None)
        self.root = self.nil
        
        
    def LeftRotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.nil:
            y.left.p = x
        y.p = x.p
        if x.p == self.nil:
            self.root = y
        elif x == x.p.left:
            x.p.left = y
        else:
            x.p.right = y
        y.left = x
        x.p = y
        
    def RightRotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.nil:
            y.right.p = x
        y.p = x.p
        if x.p == self.nil:
            self.root = y
        elif x == x.p.right:
            x.p.right = y
        else:
            x.p.left = y
        y.right = x
        x.p = y    
        
    def InsertFixup(self, z):
        while z.p.colour == 'r':
            
            if z.p == z.p.p.left:
                try:
                    y = z.p.p.right
                    if y.colour == 'r':
                        z.p.colour = 'b'
                        y.colour = 'b'
                        z.p.p.colour = 'r'
                        z = z.p.p
                    else:
                        if z == z.p.right:
                            z = z.p
                            self.LeftRotate(z)
                        z.p.colour = 'b'
                        z.p.p.colour = 'r'
                        self.RightRotate(z.p.p)
                except:
                    pass
            else:
                try:
                    y = z.p.p.left
                    if y.colour == 'r':
                        z.p.colour = 'b'
                        y.colour = 'b'
                        z.p.p.colour = 'r'
                        z = z.p.p
                    else:
                        if z == z.p.left:
                            z = z.p
                            self.RightRotate(z)
                        z.p.colour = 'b'
                        z.p.p.colour = 'r'
                        self.LeftRotate(z.p.p)
                except:
                    pass
            self.root.colour = 'b'
                
    
    def InsertNode(self, z):
        y = self.nil
        x = self.root
        
        while x != self.nil:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.p = y
        if y == self.nil:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
        z.left = self.nil
        z.right = self.nil
        z.colour = 'r'
        self.InsertFixup(z)
        
    def InsertKey(self, z):
        self.InsertNode(self.Node(z))
    
    def Search(self, key, toSearch=None):
        if toSearch == None:
            toSearch = self.root
        while toSearch != self.nil and key != toSearch.key:
            if key < toSearch.key:
                toSearch = toSearch.left
            else:
                toSearch = toSearch.right
        return toSearch

    
    class Node(object):
        def __init__(self,key=None):
            self.colour = 'b'
            self.left = None
            self.right = None
            self.key = key
            self.p = None
            
        def __str___(self):
            return str(self.key)
        
def write_tree_as_dot(t, f, show_nil=False):
    "Write the tree in the dot language format to f."
    def node_id(node):
        return 'N%d' % id(node)       
    
######################################################
# MAIN()
######################################################
  
if __name__ == "__main__":

    A = []
    r = 1024
#        for n in range(0,r+1):
#                A.append(random.randint(0,1000))
#        print 'T1', A
#        quicksort(A, 0, r)
#        heapsort(A, r)
#        print 'T2', A
    N = 25
    R = 10
    D = 50
    #T = generate_data(N,R,D)
    
    d = Data(N,R,D)
    d.roll()
    print d.getList()
    d.sort("quicksort")
    
    N = d.getN()
    l = d.getList()
    d.setHashMod(5)
    d.build_hash_table()
    
    h = d.getHashTable()
    n = d.getHashMod()
    
    
